const int N = 1e5 + 7;
bool vi[N];// 访问数组
bool isring[N];// 每一个点是否在环上
int dep[N];// 每一个点往后的最长链 不是环的情况
int ex[N];// 每一个节点的出度
int n,m,a,b;
class Solution {
public:
    vector<vector<int>> g;
    int be;
    int dfs(int p) {
        int res = 1;
        for(auto& next : g[p]) {
            if(!vi[next] && isring[next]) {
                vi[next] = true;
                res += dfs(next);
            }
        }
        return res;
    }
    int maximumInvitations(vector<int>& s) {
        n = s.size();
        g.resize(n);
        int res = 0;
        memset(dep,0,4 * n);// 最长链
        memset(vi,false,n);
        memset(isring,true,n);// 初始假设每一个都在环上
        memset(ex,0,4 * n);
        for(int i = 0;i < n;i ++) {
            g[s[i]].push_back(i);
            ex[s[i]] ++;
        }
        // 拓扑排序 求最长链
        queue<int> q;
        for(int i = 0;i < n;i ++) {
            if(!ex[i]) {
                q.push(i);
                dep[i] = 1;
                isring[i] = false;
            }
        }
        while(!q.empty()) {
            int t = q.front(); q.pop();
            ex[s[t]] --;
            if(!ex[s[t]]) dep[s[t]] = dep[t] + 1 , q.push(s[t]) , isring[s[t]] = false;
            else dep[s[t]] = dep[t];
        }
        // 深搜 求每一个环的大小
        for(int i = 0;i < n;i ++) {
            if(!vi[i] && isring[i]) {
                vi[i] = true;
                res = max(res,dfs(i));
            }
        }
        // 剩下的就是二元环的情况了
        int o = 0;
        for(int i = 0;i < n;i ++) {
            if(s[s[i]] == i) {
                // 两元环
                o += dep[i] + dep[s[i]] + 2;
            }
        }
        res = max(res,o / 2);// 每一个二元环的贡献计算了两次
        return res;
    }
};


